﻿//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    string set[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    vector<string> ret;
    string path;
    int n;
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits == "")
            return ret;
        n = digits.size();
        dfs(digits, 0);
        return ret;
    }

    void dfs(string& digits, int pos)
    {
        if (pos == n)
        {
            ret.push_back(path);
            return;
        }

        for (auto e : set[digits[pos] - '0'])
        {
            path.push_back(e);
            dfs(digits, pos + 1);
            //恢复现场
            path.pop_back();
        }
    }
};